/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package tri;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Xuan Huy
 */
public class Insertion {

    /**
     * La méthode recherche un entier dans une liste d'entiers ordonnée par la
     * méthode dichotomie.
     *
     * @param listeOrdonnee une liste d'entiers ordonnée.
     * @param element élément à rechercher dans la liste.
     * @return <code>true</code> si l'<code>element</code> est trouvé
     * dans <code>listeOrdonne</code>, <code>false</code> sinon.
     */
    public static boolean dichotomie(List<Integer> listeOrdonnee,
            Integer element) {
        int taille = listeOrdonnee.size();
        if (taille == 0) {
            return false;
        }
        if (taille == 1) {
            return listeOrdonnee.get(0).equals(element);
        }
        int k = taille / 2;
        Integer pivot = listeOrdonnee.get(k);
        /**
         * On construit les deux sous-liste à partir de la liste listeOrdonnee.
         */
        List<Integer> l1 = listeOrdonnee.subList(0, k);
        List<Integer> l2 = listeOrdonnee.subList(k, taille);
        /**
         * Si l'élément recherché est plus petit que l'élément pivot alors on
         * recherche dans la première sous-liste, sinon on recherche dans la
         * deuxième sous-liste.
         */
        if (element.compareTo(pivot) < 0) {
            return dichotomie(l1, element);
        } else {
            return dichotomie(l2, element);
        }
    }

    /**
     * La méthode insère
     * <code>element</code> dans la sous-liste de
     * <code>liste</code> délimitée par
     * <code>debut</code> et
     * <code>fin</code>. Avant l'invocation de cette méthode, il faut que la
     * sous-liste soit déjà triée dans l'ordre croissant. L'insertion du nouvel
     * élément conserve l'ordre de la sous-liste.
     *
     * @param liste une liste d'entiers.
     * @param element élément à insérer dans la liste.
     * @param debut indice de début.
     * @param fin indice de fin.
     * @throws IndexOutOfBoundsException si <code>debut</code>
     * &lt; <code>0</code> et <code>fin</code> &gt;= <code>liste.size()</code>.
     * @throws IllegalArgumentException si <code>debut &gt; fin</code>.
     */
    public static void dichotomieInsertion(List<Integer> liste, Integer element,
            int debut, int fin) throws IndexOutOfBoundsException, IllegalArgumentException {
        if (debut < 0 || fin >= liste.size()) {
            throw new IndexOutOfBoundsException();
        }
        if (debut > fin) {
            throw new IllegalArgumentException();
        }
        if (debut == fin) {
            if (element.compareTo(liste.get(fin)) < 0) {
                liste.add(fin, element);
            } else {
                liste.add(fin + 1, element);
            }
            return;
        }
        int k = (debut + fin) / 2;
        Integer pivot = liste.get(k);
        if (element.compareTo(pivot) < 0) {
            dichotomieInsertion(liste, element, debut, k);
        } else {
            dichotomieInsertion(liste, element, k + 1, fin);
        }
    }

    /**
     * La méthode trie la liste
     * <code>liste</code> dans l'ordre croissant par la méthode de tri par
     * insertion.
     *
     * @param liste une liste d'entiers.
     * @return la liste triée dans l'ordre croissant.
     */
    public static List<Integer> triInsertion(List<Integer> liste) {
        if (liste.isEmpty()) {
            return new ArrayList<>();
        }
        List<Integer> listeOrdonnee = new ArrayList<>(liste);
        for (int j = 1; j < listeOrdonnee.size(); j++) {
            Integer cle = listeOrdonnee.get(j);
            int i = j - 1;
            while (i >= 0 && listeOrdonnee.get(i).compareTo(cle) > 0) {
                listeOrdonnee.set(i + 1, listeOrdonnee.get(i));
                i--;
            }
            listeOrdonnee.set(i + 1, cle);
        }
        return listeOrdonnee;
    }

    /**
     * La méthode fait la même chose que
     * {@link tri.Insertion#triInsertion(java.util.List)}, avec une meilleure
     * performance. L'insertion se fait par la méthode de dichotomie.
     *
     * @param liste une liste d'entiers.
     * @return la liste triée dans l'ordre croissant.
     */
    public static List<Integer> triInsertionAvance(List<Integer> liste) {
        if (liste.isEmpty()) {
            return new ArrayList<>();
        }
        List<Integer> listeOrdonnee = new ArrayList<>(liste);
        for (int j = 1; j < listeOrdonnee.size(); j++) {
            Integer cle = listeOrdonnee.remove(j);
            int i = j - 1;
            dichotomieInsertion(listeOrdonnee, cle, 0, i);
        }
        return listeOrdonnee;
    }
}
